package NO3_LinkedList;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 2025-08-29
 * 力扣 - 61. 旋转链表
 * <p>
 * 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
 */
public class RotateRightMain {
    public static void main(String[] args) {
        ListNode head = new ListNode(
                1,
                new ListNode(2,
                        new ListNode(3,
                                new ListNode(4,
                                        new ListNode(5)))));
        ListNode.printList(rotateRight(head, 2));
    }

    // 使用队列存储所有节点，将后k个节点移到队列前面，重新构建链表
    public static ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) {
            return head;
        }

        // 使用队列存储所有节点
        Deque<ListNode> deque = new ArrayDeque<>();
        ListNode cur = head;
        int length = 0;

        // 将节点加入队列并计算长度
        while (cur != null) {
            deque.offer(cur);
            cur = cur.next;
            length++;
        }

        // 处理k值，防止k大于链表长度
        k = k % length;
        if (k == 0) {
            return head;
        }

        // 将后k个节点移到队列前面
        for (int i = 0; i < length - k; i++) {
            ListNode node = deque.poll();
            deque.offer(node);
        }

        // 重新构建链表
        ListNode newHead = deque.poll();
        ListNode current = newHead;

        while (!deque.isEmpty()) {
            current.next = deque.poll();
            current = current.next;
        }

        // 将最后一个节点的next设为null，防止循环链表
        current.next = null;

        return newHead;
    }
}
